- Title
- C-graph automatic groups
- Creator
- Elder, Murray; Taback, Jennifer
- Relation
- ARC.FT110100178 http://purl.org/au-research/grants/arc/FT110100178
- Relation
- Journal of Algebra Vol. 413, p. 289-319
- Publisher Link
- http://dx.doi.org/10.1016/j.jalgebra.2014.04.021
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2014
- Description
- We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov by replacing the regular languages in their definition with more powerful language classes. For a fixed language class C, we call the resulting groups C-graph automatic. We prove that the class of C-graph automatic groups is closed under change of generating set, direct and free product for certain classes C. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompson's groups F, T and V.
- Subject
- automatic group; Cayley graph automatic group; context-sensitive language; polynomial time algorithm; counter language
- Identifier
- http://hdl.handle.net/1959.13/1043495
- Identifier
- uon:14202
- Identifier
- ISSN:0021-8693
- Rights
- © 2014. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/.
- Language
- eng
- Full Text
- Reviewed
- Hits: 1326
- Visitors: 1645
- Downloads: 330
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | ATTACHMENT02 | Author final version | 471 KB | Adobe Acrobat PDF | View Details Download |